// 运用unordered_map将元素索引记录下来
// 对nums中元素遍历，如果存在target - nums[i]的元素，则返回其索引
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> index;
    int n = nums.size();

    for (int i = 0; i < n; i++) {
        unordered_map<int, int>::iterator it = index.find(target - nums[i]);
        if (it != index.end())
            return {it->second, i};
        index[nums[i]] = i;
    }
    return {};
}

class TwoSum {
public:
    void add(int number) {
        // 记录数组中number出现次数
        freq[number]++;
    }

    bool find(int value) {
        for (unordered_map<int, int>::iterator it = freq.begin(); it != freq.end(); it++) {
            int other = value - it->first;
            // 如果value = other * 2;
            if (other == it->first && freq[it->first] > 1)
                return true;
            // 如果other != it->first
            if (other != it->first && freq.count(other))
                return true;
        }
        return false;
    }
private:
    unordered_map<int, int> freq;
};

class TwoSum2 {
public:
    void add(int number) {
        // 记录下所有可能的和
        for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++)
            sums.insert(*it + number);
        nums.push_back(number);
    }

    bool find(int value) {
        return sums.count(value);
    }
private:
    set<int> sums;
    vector<int> nums;
};

